package zuoshen_video2.dynamic;

import java.util.Arrays;

import org.junit.Test;

import utils.ArrayGenerator;

//最大子序和，简单题中的
public class MaxSubarraySum {
    
    class Solution {
        public int maxSubArray(int[] nums) {
            int len = nums.length;
            if (len == 0) return 0;
            int[] yes = new int[len], no = new int[len];
            yes[0] = nums[0];
            no[0] = 0;

            for (int i = 1; i < len; i++) {
                yes[i] = Math.max(yes[i - 1] + nums[i], nums[i]);
                no[i] = Math.max(no[i - 1], yes[i - 1]);
            }

            return Math.max(yes[len - 1], no[len - 1]);
        }

        public int maxSubArray2(int[] nums) {
            int len = nums.length;
            if (len == 0) return 0;
            int yes = nums[0];
            int no = 0;

            for (int i = 1; i < len; i++) {
                int temp = yes;
                yes = Math.max(yes + nums[i], nums[i]);
                no = Math.max(no, temp);
            }

            return Math.max(yes, no);
        }
    }

    @Test
    public void test() {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        Solution s = new Solution();
        System.out.println(s.maxSubArray(nums));

        for (int i = 0; i < 100000; i++) {
            nums = ArrayGenerator.getArray(-10000, 10000, 100);
            if (s.maxSubArray(nums) != s.maxSubArray2(nums)) {
                System.out.println(Arrays.toString(nums));
            }
        }
        System.out.println("yes");
    }
}
